/*
 * @lc app=leetcode.cn id=1289 lang=cpp
 *
 * [1289] 下降路径最小和  II
 *
 * https://leetcode.cn/problems/minimum-falling-path-sum-ii/description/
 *
 * algorithms
 * Hard (61.38%)
 * Likes:    194
 * Dislikes: 0
 * Total Accepted:    38.3K
 * Total Submissions: 62.4K
 * Testcase Example:  '[[1,2,3],[4,5,6],[7,8,9]]'
 *
 * 给你一个 n x n 整数矩阵 grid ，请你返回 非零偏移下降路径 数字和的最小值。
 *
 * 非零偏移下降路径 定义为：从 grid 数组中的每一行选择一个数字，且按顺序选出来的数字中，相邻数字不在原数组的同一列。
 *
 *
 *
 * 示例 1：
 *
 *
 *
 *
 * 输入：grid = [[1,2,3],[4,5,6],[7,8,9]]
 * 输出：13
 * 解释：
 * 所有非零偏移下降路径包括：
 * [1,5,9], [1,5,7], [1,6,7], [1,6,8],
 * [2,4,8], [2,4,9], [2,6,7], [2,6,8],
 * [3,4,8], [3,4,9], [3,5,7], [3,5,9]
 * 下降路径中数字和最小的是 [1,5,7] ，所以答案是 13 。
 *
 *
 * 示例 2：
 *
 *
 * 输入：grid = [[7]]
 * 输出：7
 *
 *
 *
 *
 * 提示：
 *
 *
 * n == grid.length == grid[i].length
 * 1 <= n <= 200
 * -99 <= grid[i][j] <= 99
 *
 *
 */
#include <bits/stdc++.h>
using namespace std;
// @lc code=start
class Solution {
public:
    int minFallingPathSum(vector<vector<int>>& grid) {
        int n = grid.size();
        if (n == 1) return grid[0][0];

        vector<vector<int>> dp(n - 1, vector<int>(n, 0));
        dp.insert(dp.begin(), grid[0]);

        for (int i = 1; i < n; i++) {

            // 存储上一层最小的两个值
            int f = dp[i - 1][0] < dp[i - 1][1] ? 0 : 1, s = 1 - f;
            for (int j = 2; j < n; j++) {
                if(dp[i - 1][j] < dp[i - 1][f]){
                    s = f;
                    f = j;
                }else if(dp[i - 1][j] < dp[i - 1][s]){
                    s = j;
                }
            }
            for (int j = 0; j < n; j++) {
                // 存储最小值后不用每次都遍历上一层dp了
                dp[i][j] = (j == f ? dp[i - 1][s] : dp[i - 1][f]) + grid[i][j];
            }
        }
        return *(min_element(dp[n - 1].begin(), dp[n - 1].end()));
    }
};
// @lc code=end
